package com.hdu.other.dp.statusDP;


import java.util.Arrays;

public class lc698 {
    class Solution {
        public boolean canPartitionKSubsets(int[] nums, int k) {
            int sum = 0;
            for (int num : nums) {
                sum += num;
            }
            if (sum % k != 0) {
                return false;
            }
            int avg = sum / k;
            int status = (1 << nums.length) - 1;
            int[] dp = new int[1 << nums.length];
            Arrays.fill(dp, -1);
            return f(nums, status, dp, k, avg, avg);
        }

        boolean f(int[] nums, int status, int[] dp, int k, int avg, int cur) {
            if (k == 0) {
                return status == 0;
            }
            if (dp[status] != -1) {
                return dp[status] == 1;
            }
            boolean ans = false;
            for (int i = 0; i < nums.length; i++) {
                if ((status & (i << 1)) != 0 && cur >= nums[i]) {
                    int leave = cur - nums[i];
                    if (leave == 0) {
                        ans = f(nums, status ^ (1 << i), dp, k - 1, avg, avg);
                    } else {
                        ans = f(nums, status ^ (1 << i), dp, k, avg, leave);
                    }
                    if (ans) {
                        break;
                    }
                }
            }
            dp[status] = ans ? 1 : 0;
            return ans;
        }
    }
}
